A cache memory can be constructed in many ways. Initially, the cache is empty, and the cache elements can be conceived as having pointers to the beginning and the end of the cache. These pointers are referred to as the head and tail pointers. The head pointer points to the next available cache line (newest), whereas the tail pointer points to the beginning, or oldest cache line within the cache. As rasterization of a display occurs, the head pointer is incremented as cache misses occur, until the cache fills. Then, the head pointer wraps to the beginning or oldest cache line, and the tail pointer is incremented. This concept is referred to as a circular buffer.
A cache line has associated tags, which track to memory pages, banks, and discreet memory locations within each page/bank group. As prefetching or cache misses occur, current or subsequent cache items may actually point to memory locations with no spatial coherence to each other (i.e., on different memory pages/addresses).
Using an LRU approach, cache line replacement would be forced to incur a page access, possibly degrading system memory performance while the memory subsystem starts the new (or old) cache memory page. This problem might be exaggerated if the cache line to be replaced must first be written out, and it is on a totally different memory page. The system performance degradation is due to the time associated with memory page crossings.
Therefore, there is a need in the art for an improved cache line replacement technique, which improves upon the prior art LRU method.